The present invention describes improvements to the Perlin Noise function. These improvements: (i) improve the appearance of Perlin Noise, greatly reducing artifacts that were present in the original version, and (ii) allow for an efficient implementation at gate-level hardware, thereby facilitating performance improvement by a factor of 1000 over the software implementation now in common use.
Perlin Noise as originally described in Perlin, K., An Image Synthesizer, Computer Graphics; Vol. 19 No. 3, incorporated by reference herein, contained noticeable visual artifacts due to the simple way that gradients were chosen and blended. These artifacts are specifically removed by the present invention.
Also, without the improvements described in the present invention, a gate-level implementation of Perlin Noise would be prohibitively expensive and impractical, requiring many tens of thousands of gates and a throughput of only one evaluation per many clock cycles. With the improvements disclosed in present invention, Perlin Noise can be implemented in under 10000 hardware gates, with an optimal throughput of one evaluation per clock cycle.
Perlin Noise (Perlin, K., An Image Synthesizer, Computer Graphics; Vol. 19 No. 3, incorporated by reference herein), developed by the present inventor, is a method for synthesizing a coherent band-limited noise signal over an n dimensional geometric space Rn. Because Perlin Noise is repeatable, approximately isotropic, pseudo-random and band-limited, it can be used to synthesize signals with desired mixtures of spatial frequency. Because the resulting synthesized textures are very customizable and look naturalistic, Perlin Noise has proven to be a versatile tool for a number of synthesis applications.
The theoretical foundation for Perlin Noise, described by Perlin, K., Synthesizing Realistic Textures through the Composition of Perceptually Motivated Functions, Ph.D. Dissertation, New York University, 1986, incorporated by reference herein, is grounded in the fact that human perception is quite sensitive to spatial frequency (“Vision: a computational investigation into the human representation and processing of visual information”, Marr, D., W.H. Freeman, San Francisco, Calif., 1982, incorporated by reference herein). That is, humans can readily distinguish items within the visual field based on scale. Perlin Noise implements a signal which has three properties: (i) It is pseudo-random—its value is uncorrelated between any two domain points which are greater than a unit distance from each other. (ii) It is approximately isotropic—statistically the same in all directions. (iii) It is band limited—most of its energy is confined to a single octave of the frequency spectrum.
This combination of features gives a tool to programmer/artists who wish to create the appearance of textures, that is highly controllable. Differently scaled instances of the Perlin Noise function can simply be summed together or combined through functional composition with simple analytic functions.
The original implementation of Perlin Noise is a pseudo-random spline over Rn. Given an input point, the original algorithm retrieves a pseudo-random gradient vector at each of the 2n vertices of the integer-valued hypercube that surrounds the point. Then these gradient vectors are combined by cubic interpolation to produce a value for that input point.
This algorithm only approximates the properties enumerated above. In particular, because the lattice point indices are mapped to gradient directions in a uniformly random way, nothing prevents adjoining lattice points from being mapped to very similar gradient directions. Where this occurs, an unwanted visual correlation appears in the vicinity of those lattice points.
In addition, the signal produced is only approximately isotropic. Because the pseudo-random gradients are chosen uniformly in direction, the appearance of the final signal is noticeably different along the major coordinate axes, along which lattice points are spaced more closely together, than it is in off-axis directions, where the distance between successive lattice points is larger.
Furthermore, a single evaluation of Perlin Noise required a fairly large number of multiplies. Most of these multiplies are necessitated by the need to perform a vector inner product between the gradient vector at each of 2n lattice points, and the difference vector from each of those lattice points to the input point. This alone requires n2n multiplies, in addition to the 2n−1 multiplies required for the n dimensional spline interpolation. The large number of multiplies required to effect these inner products precludes a practical port of the original Perlin Noise algorithm to the gate-array hardware level.
Currently, the most prevalent use of Perlin Noise is in the synthesis of natural-appearing materials for computer graphics, in which case it is generally used over R3. In this context, Perlin Noise has been an integral part of the computer graphics rendering portion of all commercial 3D software packages for the last ten years. Some of these commercial packages are RenderMan, Alias, SoftImage, Caligari, Kai's Power Tools, and Dynamation. A broad range of texture effects have been developed based on Perlin Noise, many of which are described in Texturing and Modeling; A Procedural Approach, Second Edition; Ebert D. et al, AP Professional; Cambridge 1998, incorporated by reference herein. These texture effects are now used widely in the field of visual simulation, particularly for special effects in motion pictures and television commercials. Because of this wide use, the inventor received a Technical Achievement award by the Academy of Motion Picture Arts and Sciences (Technical Achievement Award from the Academy of Motion Picture Arts and Sciences, “for the development of Perlin Noise, a technique used to produce natural appearing textures on computer generated surfaces for motion picture visual effects.”, incorporated by reference herein).
In addition to being used within computer graphic software shaders to simulate the physical appearance of objects, Perlin Noise is also used to animate synthetic objects. For example, the synthesized trees in the motion picture Twister were animated at Industrial Light and Magic, a special effects company, by moving three dimensional Perlin Noise past the trees and using the gradient field of the noise as simulated force vectors, thereby making the trees appear to sway in the wind.
Even though it has found wide use in the field of visual simulation, the Perlin Noise function would find far wider use if it were many times faster. Because of the number of operations required to implement Perlin Noise in software, it cannot currently be used for a number of important applications.
For example, ten years ago the present inventor demonstrated the technique of space-filling textures built from Perlin Noise. These were rendered by taking many direct samples within a three dimensional volume. This technique was shown to simulate a wide variety of solid materials, including hair, fire, cloth, rock, and eroded metals (Perlin, K., and Hoffert, E., Hypertexture, 1989 Computer Graphics (proceedings of ACM SIGGRAPH Conference); Vol. 23 No. 3, incorporated by reference herein). Because such applications require computation at each point in a volume, the computational requirements were too great for most current commercial applications.
Also, real-time computer-simulated games do not yet employ Perlin Noise directly. This is because real-time game play requires the production of 30 to 60 highly textured images per second. Using a software implementation of Perlin Noise, this would require more computation than is currently available on personal computers. For this reason, current practice in the real-times game industry is to prerender materials generated with software shaders that use Perlin Noise, and then to use texture mapping techniques to place these on objects in the scene.
It would be highly desirable to remove this preproduction step, and instead to generate textures based on Perlin Noise directly, and in real time. This would allow game designers to reduce texture storage costs dramatically. Also, it would allow game players to move arbitrarily close to textured objects. Currently, texture-mapped objects in computer games become blurry in appearance when the simulated viewpoint approaches near enough so that the resolution of the texture-mapped image provides insufficient detail. Procedural textures based on Perlin Noise do not suffer from this deficiency, because higher spatial frequencies can always be computed to provide the needed detail, no matter how close the player moves.
Another disadvantage of stored textures is the need to create an explicit mapping from the two dimensional texture image to the three dimensional form of the simulated object. Procedural textures based on Perlin Noise do not have this deficiency, because the (X,Y,Z) coordinate of the object provides a direct index into the texture function, without requiring the use of an intermediate mapped image.
Also, if procedural textures based on Perlin Noise can be computed in real-time in computer games, then they can be used to create many dynamic effects such as clouds, fire, water, smoke, and heat shimmer, which can at best only be approximated with other methods.
All of the above-mentioned advantages to be gained from a real-time implementation of Perlin Noise are equally relevant for real-time military and medical simulators, real-time weather simulation, and the emerging field of simulation of natural materials for high definition and interactive broadcast television.
The Intel corporation has developed a version of Perlin Noise that takes advantage of the SIMD processing available on their MMX accelerator chip (Using MMX[tm] Instructions for Procedural Texture Mapping, Intel Developer Relations Group, Version 1.0, Nov. 18, 1996, http://developer.intel.com/drq/mmx/appnotes/proctex.htm, incorporated by reference herein). That implementation handles only the case of Perlin Noise over R2, not over R3. The distinction is important because noise over two dimensions provides only marginal advantages over texture mapping, whereas noise over three dimensions, for which hardware implementation is enabled by the present invention, provides texturing capabilities that are fundamentally unattainable through the use of traditional texture mapping approaches. In addition, the Intel/MMX implementation is not a hardware implementation per se, but rather a software implementation that takes advantage of the MMX architecture. As such, it requires 32 clock cycles per 2D evaluation, whereas the present invention requires only one clock cycle per 3D evaluation.